package com.zy.str;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author zhaoyi
 * @date 2022/1/24 4:05 下午
 * <p>
 * 坏字符规则
 * 好后缀规则--可以不用这个复杂的东西,简单点就移动一位 牺牲点性能
 * https://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf
 */
public class BMMatch {

    /**
     * @param source 主串
     * @param m      模式串
     */
    public static boolean match(char[] source, char[] m) {
        int k = 1;

        //模式串构建一个便捷查询的
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < m.length; i++) {
            //后面更大直接put
            map.put(m[i], i);
        }

        //从右向左, 主串最右下标
        int s = m.length - 1;
        while (s <= (source.length - 1)) {
            System.out.println("===== 开始第 " + k++ + " 轮匹配 =========");
            boolean flag = true;

            //从右往左
            for (int i = (m.length - 1); i >= 0; i--) {
                char mc = m[i];
                int si = s - (m.length - 1 - i);
                System.out.println("  模式串下标" + i + " ,主串下标" + si);
                char sc = source[si];
                if (mc != sc) {
                    //出现不匹配
                    Integer x = map.getOrDefault(sc, -1);
                    //滑动位数
                    int le = i - x;
                    if (le < 0) {
                        System.out.println(" ********不用好后缀, 简单点就滑动一位即可******");
                        le = 1;
                    }
                    s = s+le;
                    System.out.println("  滑动位数>>" + le + " 主串最左下标 " + s);
                    flag = false;
                    //跳出模式串匹配循环
                    break;
                }
            }

            if (flag){
                return true;
            }

        }

        return false;
    }


    public static void main(String[] args) {
        //G T T A T A G C T G A T C G C G G C G T A G C G G C G A A
        //G T A G C G G C G
        char[] source = {'G', 'T', 'T', 'A', 'T', 'A', 'G', 'C', 'T', 'G', 'A', 'T', 'C', 'G', 'C', 'G', 'G', 'C', 'G', 'T', 'A', 'G', 'C', 'G', 'G', 'C', 'G', 'A', 'A'};
        //char[] m = {'C', 'G', 'A', 'A'};
        //char[] m = {'G', 'T', 'A', 'G', 'C', 'G', 'G', 'C', 'G'};
        char[] m = {'C', 'G', 'A', 'F'};
        System.out.println(match(source, m));
    }

}
